This track of the course covers the topic "Queue".
In details, this track will cover:
Objective: The objective of this track is to familiarize the learners with Queue.
Track Content:
Assessment: All Tracks in every week are associated with weekly contests.
Through this video, we will learn the Implementation of a queue using an array.
Codes:
Through this video, we will learn the Implementation of a queue using a LinkedList.
Codes:
This video discusses the implementation of Queue in C++ STL. We will also learn various operations that the Queue STL libraries have to provide.
Codes:
In this video we'll talk about Queue in Java
Codes:
This video discusses the implementation of the stack using a queue.
Codes:
This video discusses the efficient approach of Reversing a Queue.
Codes:
This video discusses the below problem:
Given a number n, print first n number(in increasing order) such that all these numbers have digits in set {5, 6}
Codes:
Array = queue[N].
front = 0, rear = N-1.
N = 5.
Operation 1:
enque(5);
front = 0,
rear = (N-1 + 1)%N = 0.
Queue contains: [5].
Operation 2:
enque(10);
front = 0,
rear = (rear + 1)%N = (0 + 1)%N = 1.
Queue contains: [5, 10].
Operation 3:
enque(15);
front = 0,
rear = (rear + 1)%N = (1 + 1)%N = 2.
Queue contains: [5, 10, 15].
Operation 4:
deque();
print queue[front];
front = (front + 1)%N = (0 + 1)%N = 1.
Queue contains: [10, 15].
// CPP program for array implementation of queue
#include <bits/stdc++.h>
using namespace std;
// A structure to represent a queue
class Queue
{
public:
int front, rear, size;
unsigned capacity;
int* array;
};
// function to create a queue of a given capacity.
// It initializes the size of the queue as 0
Queue* createQueue(unsigned capacity)
{
Queue* queue = new Queue();
queue->capacity = capacity;
queue->front = queue->size = 0;
queue->rear = capacity - 1; // This is important, see the enqueue
queue->array = new int[(queue->capacity * sizeof(int))];
return queue;
}
// Queue is full when size
// becomes equal to the capacity
int isFull(Queue* queue)
{ return (queue->size == queue->capacity); }
// Queue is empty when size is 0
int isEmpty(Queue* queue)
{ return (queue->size == 0); }
// Function to add an item to the queue.
// It changes rear and size
void enqueue(Queue* queue, int item)
{
if (isFull(queue))
return;
queue->rear = (queue->rear + 1) % queue->capacity;
queue->array[queue->rear] = item;
queue->size = queue->size + 1;
cout << item << " enqueued to queue\n";
}
// Function to remove an item from the queue.
// It changes front and size
int dequeue(Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
int item = queue->array[queue->front];
queue->front = (queue->front + 1) % queue->capacity;
queue->size = queue->size - 1;
return item;
}
// Function to get front of queue
int front(Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->front];
}
// Function to get rear of queue
int rear(Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->rear];
}
// Driver code
int main()
{
Queue* queue = createQueue(1000);
enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);
enqueue(queue, 40);
cout<<dequeue(queue)<<" dequeued from queue\n";
cout << "Front item is " << front(queue) << endl;
cout << "Rear item is " << rear(queue) << endl;
return 0;
}
// Java program for array implementation of queue
// A class to represent a queue
class Queue
{
int front, rear, size;
int capacity;
int array[];
public Queue(int capacity) {
this.capacity = capacity;
front = this.size = 0;
rear = capacity - 1;
array = new int[this.capacity];
}
// Queue is full when size becomes equal to
// the capacity
boolean isFull(Queue queue)
{ return (queue.size == queue.capacity);
}
// Queue is empty when size is 0
boolean isEmpty(Queue queue)
{ return (queue.size == 0); }
// Method to add an item to the queue.
// It changes rear and size
void enqueue( int item)
{
if (isFull(this))
return;
this.rear = (this.rear + 1)%this.capacity;
this.array[this.rear] = item;
this.size = this.size + 1;
System.out.println(item+ " enqueued to queue");
}
// Method to remove an item from queue.
// It changes front and size
int dequeue()
{
if (isEmpty(this))
return Integer.MIN_VALUE;
int item = this.array[this.front];
this.front = (this.front + 1)%this.capacity;
this.size = this.size - 1;
return item;
}
// Method to get front of queue
int front()
{
if (isEmpty(this))
return Integer.MIN_VALUE;
return this.array[this.front];
}
// Method to get rear of queue
int rear()
{
if (isEmpty(this))
return Integer.MIN_VALUE;
return this.array[this.rear];
}
}
// Driver class
public class Test
{
public static void main(String[] args)
{
Queue queue = new Queue(1000);
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
System.out.println(queue.dequeue() +
" dequeued from queue\n");
System.out.println("Front item is " +
queue.front());
System.out.println("Rear item is " +
queue.rear());
}
}
10 enqueued to queue
20 enqueued to queue
30 enqueued to queue
40 enqueued to queue
10 dequeued from queue
Front item is 20
Rear item is 40
queue< data_type > queue_name;
where,
data_type is the type of element to be stored
in the queue.
queue_name is the name of the queue data structure.
The queue gquiz is : 10 20 30
gquiz.size() : 3
gquiz.front() : 10
gquiz.back() : 30
gquiz.pop() : 20 30
Elements of queue-[0, 1, 2, 3, 4]
removed element-0
[1, 2, 3, 4]
head of queue-1
Size of queue-4
A circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.


Why have we taken a pointer that points to the last node instead of first node?
For insertion of node in the beginning we need to traverse the whole list. Also, for insertion at the end, the whole list has to be traversed. If instead of start pointer we take a pointer to the last node then in both the cases there won’t be any need to traverse the whole list. So, insertion in the begging or at the end takes constant time irrespective of the length of the list.
// A complete C++ program to demonstrate the
// working of Circular Linked Lists
#include<bits/stdc++.h>
using namespace std;
// Circular Linked List Node
struct Node
{
int data;
struct Node *next;
};
// Function to add a node at the end of a
// Circular Linked List
struct Node *addEnd(struct Node *last, int data)
{
if (last == NULL)
{
// Creating a node dynamically.
struct Node *temp = new Node;
// Assigning the data.
temp -> data = data;
last = temp;
// Creating the link.
last -> next = last;
return last;
}
struct Node *temp = new Node;
temp -> data = data;
temp -> next = last -> next;
last -> next = temp;
last = temp;
return last;
}
// Function to traverse a Circular Linked list
// Using a pointer to the Last Node
void traverse(struct Node *last)
{
struct Node *p;
// If list is empty, return.
if (last == NULL)
{
cout << "List is empty." << endl;
return;
}
// Pointing to first Node of the list.
p = last -> next;
// Traversing the list.
do
{
cout << p -> data << " ";
p = p -> next;
}
while(p != last->next);
}
// Driver Program
int main()
{
struct Node *last = NULL;
last = addEnd(last, 6);
last = addEnd(last, 4);
last = addEnd(last, 2);
last = addEnd(last, 8);
last = addEnd(last, 12);
last = addEnd(last, 10);
traverse(last);
return 0;
}
// A complete Java program to demonstrate the
// working of Circular Linked Lists
class CLL
{
// A circular linked list node
static class Node
{
int data;
Node next;
};
// Function to insert a node in a Circular
// linked list at the end
static Node addEnd(Node last, int data)
{
if (last == null)
{
// Creating a node dynamically.
Node temp = new Node();
// Assigning the data.
temp.data = data;
last = temp;
// Creating the link.
last.next = last;
return last;
}
Node temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
last = temp;
return last;
}
// Function to traverse a given Circular Linked
// List using the Last pointer
static void traverse(Node last)
{
Node p;
// If list is empty, return.
if (last == null)
{
System.out.println("List is empty.");
return;
}
// Pointing to first Node of the list.
p = last.next;
// Traversing the list.
do
{
System.out.print(p.data + " ");
p = p.next;
}
while(p != last.next);
}
// Driver code
public static void main(String[] args)
{
Node last = null;
last = addEnd(last, 6);
last = addEnd(last, 4);
last = addEnd(last, 2);
last = addEnd(last, 8);
last = addEnd(last, 12);
last = addEnd(last, 10);
traverse(last);
}
}
6 4 2 8 12 10

push(s, x) // x is the element to be pushed and s is stack
1) Enqueue x to q2
2) One by one dequeue everything from q1 and enqueue to q2.
3) Swap the names of q1 and q2
// Swapping of names is done to avoid one more
// movement of all elements from q2 to q1.
pop(s)
1) Dequeue an item from q1 and return it.
// C++ pogram to implement a stack using
// two queues
#include<bits/stdc++.h>
using namespace std;
// Stack class
class Stack
{
// Two inbuilt queues
queue<int> q1, q2;
// To maintain current number of
// elements
int curr_size;
public:
Stack()
{
curr_size = 0;
}
// Function to implement push() operation
void push(int x)
{
curr_size++;
// Push x first in empty q2
q2.push(x);
// Push all the remaining
// elements in q1 to q2.
while (!q1.empty())
{
q2.push(q1.front());
q1.pop();
}
// swap the names of two queues
queue<int> q = q1;
q1 = q2;
q2 = q;
}
// Function to implement pop() operation
void pop(){
// if no elements are there in q1
if (q1.empty())
return ;
q1.pop();
curr_size--;
}
// Function to return top element
// of implemented Stack
int top()
{
if (q1.empty())
return -1;
return q1.front();
}
// Function to return size of stack
int size()
{
return curr_size;
}
};
// Driver code
int main()
{
Stack s;
s.push(1);
s.push(2);
s.push(3);
cout << "current size: " << s.size()
<< endl;
cout << s.top() << endl;
s.pop();
cout << s.top() << endl;
s.pop();
cout << s.top() << endl;
cout << "current size: " << s.size()
<< endl;
return 0;
}// Java Program to implement a stack using
// two queue
import java.util.*;
class GfG
{
static class Stack
{
// Two inbuilt queues
static Queue<Integer> q1 = new LinkedList<Integer>();
static Queue<Integer> q2 = new LinkedList<Integer>();
// To maintain current number of
// elements
static int curr_size;
Stack()
{
curr_size = 0;
}
// Method to implement push() operation
static void push(int x)
{
curr_size++;
// Push x first in empty q2
q2.add(x);
// Push all the remaining
// elements in q1 to q2.
while (!q1.isEmpty())
{
q2.add(q1.peek());
q1.remove();
}
// swap the names of two queues
Queue<Integer> q = q1;
q1 = q2;
q2 = q;
}
// Method to implement pop() operation
static void pop(){
// if no elements are there in q1
if (q1.isEmpty())
return ;
q1.remove();
curr_size--;
}
// Method to get the top element of Stack
static int top()
{
if (q1.isEmpty())
return -1;
return q1.peek();
}
// Method to find the size of the Stack
static int size()
{
return curr_size;
}
};
// Driver Code
public static void main(String[] args)
{
Stack s = new Stack();
s.push(1);
s.push(2);
s.push(3);
System.out.println("current size: " + s.size());
System.out.println(s.top());
s.pop();
System.out.println(s.top());
s.pop();
System.out.println(s.top());
System.out.println("current size: " + s.size());
}
} current size: 3
3
2
1
current size: 1
push(s, x)
1) Enqueue x to q1 (assuming size of q1 is unlimited).
pop(s)
1) One by one dequeue everything except the last element
from q1 and enqueue to q2.
2) Dequeue the last item of q1, the dequeued item
is the result, store it.
3) Swap the names of q1 and q2
4) Return the item stored in step 2.
// Swapping of names is done to avoid one more
// movement of all elements from q2 to q1.
// Program to implement a stack using two queues
#include<bits/stdc++.h>
using namespace std;
// Stack class
class Stack
{
queue<int> q1, q2;
int curr_size;
public:
Stack()
{
curr_size = 0;
}
void pop()
{
if (q1.empty())
return;
// Leave one element in q1 and
// push others in q2.
while (q1.size() != 1)
{
q2.push(q1.front());
q1.pop();
}
// Pop the only left element
// from q1
q1.pop();
curr_size--;
// swap the names of two queues
queue<int> q = q1;
q1 = q2;
q2 = q;
}
void push(int x)
{
q1.push(x);
curr_size++;
}
int top()
{
if (q1.empty())
return -1;
while( q1.size() != 1 )
{
q2.push(q1.front());
q1.pop();
}
// last pushed element
int temp = q1.front();
// to empty the auxiliary queue after
// last operation
q1.pop();
// push last element to q2
q2.push(temp);
// swap the two queues names
queue<int> q = q1;
q1 = q2;
q2 = q;
return temp;
}
int size()
{
return curr_size;
}
};
// Driver code
int main()
{
Stack s;
s.push(1);
s.push(2);
s.push(3);
s.push(4);
cout << "current size: " << s.size()
<< endl;
cout << s.top() << endl;
s.pop();
cout << s.top() << endl;
s.pop();
cout << s.top() << endl;
cout << "current size: " << s.size()
<< endl;
return 0;
}current size: 4
4
3
2
current size: 2

enQueue(q, x)
1) While stack1 is not empty, push everything from stack1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.
Here the time complexity will be O(n)
deQueue(q)
1) If stack1 is empty then print an error
2) Pop an item from stack1 and return it
Here time complexity will be O(1)
// CPP program to implement Queue using
// two stacks with costly enQueue()
#include <bits/stdc++.h>
using namespace std;
struct Queue {
stack<int> s1, s2;
void enQueue(int x)
{
// Move all elements from s1 to s2
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
// Push item into s1
s1.push(x);
// Push everything back to s1
while (!s2.empty()) {
s1.push(s2.top());
s2.pop();
}
}
// Dequeue an item from the queue
int deQueue()
{
// if first stack is empty
if (s1.empty()) {
cout << "Q is Empty";
exit(0);
}
// Return top of s1
int x = s1.top();
s1.pop();
return x;
}
};
// Driver code
int main()
{
Queue q;
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
cout << q.deQueue() << '\n';
cout << q.deQueue() << '\n';
cout << q.deQueue() << '\n';
return 0;
}// Java program to implement Queue using
// two stacks with costly enQueue()
import java.util.*;
class GFG
{
static class Queue
{
static Stack<Integer> s1 = new Stack<Integer>();
static Stack<Integer> s2 = new Stack<Integer>();
static void enQueue(int x)
{
// Move all elements from s1 to s2
while (!s1.isEmpty())
{
s2.push(s1.pop());
//s1.pop();
}
// Push item into s1
s1.push(x);
// Push everything back to s1
while (!s2.isEmpty())
{
s1.push(s2.pop());
//s2.pop();
}
}
// Dequeue an item from the queue
static int deQueue()
{
// if first stack is empty
if (s1.isEmpty())
{
System.out.println("Q is Empty");
System.exit(0);
}
// Return top of s1
int x = s1.peek();
s1.pop();
return x;
}
};
// Driver code
public static void main(String[] args)
{
Queue q = new Queue();
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
System.out.println(q.deQueue());
System.out.println(q.deQueue());
System.out.println(q.deQueue());
}
} 1
2
3
enQueue(q, x)
1) Push x to stack1 (assuming size of stacks is unlimited).
Here time complexity will be O(1)
deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from stack1 to stack2.
3) Pop the element from stack2 and return it.
Here time complexity will be O(n)
// CPP program to implement Queue using
// two stacks with costly deQueue()
#include <bits/stdc++.h>
using namespace std;
struct Queue {
stack<int> s1, s2;
// Enqueue an item to the queue
void enQueue(int x)
{
// Push item into the first stack
s1.push(x);
}
// Dequeue an item from the queue
int deQueue()
{
// if both stacks are empty
if (s1.empty() && s2.empty()) {
cout << "Q is empty";
exit(0);
}
// if s2 is empty, move
// elements from s1
if (s2.empty()) {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
}
// return the top item from s2
int x = s2.top();
s2.pop();
return x;
}
};
// Driver code
int main()
{
Queue q;
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
cout << q.deQueue() << '\n';
cout << q.deQueue() << '\n';
cout << q.deQueue() << '\n';
return 0;
}// Java Program to implement a queue using two stacks
// Note that Stack class is used for Stack implementation
import java.util.Stack;
public class GFG {
/* class of queue having two stacks */
static class Queue {
Stack<Integer> stack1;
Stack<Integer> stack2;
}
/* Function to push an item to stack*/
static void push(Stack<Integer> top_ref, int new_data)
{
// Push the data onto the stack
top_ref.push(new_data);
}
/* Function to pop an item from stack*/
static int pop(Stack<Integer> top_ref)
{
/*If stack is empty then error */
if (top_ref.isEmpty()) {
System.out.println("Stack Underflow");
System.exit(0);
}
// pop the data from the stack
return top_ref.pop();
}
// Function to enqueue an item to the queue
static void enQueue(Queue q, int x)
{
push(q.stack1, x);
}
/* Function to deQueue an item from queue */
static int deQueue(Queue q)
{
int x;
/* If both stacks are empty then error */
if (q.stack1.isEmpty() && q.stack2.isEmpty()) {
System.out.println("Q is empty");
System.exit(0);
}
/* Move elements from stack1 to stack 2 only if
stack2 is empty */
if (q.stack2.isEmpty()) {
while (!q.stack1.isEmpty()) {
x = pop(q.stack1);
push(q.stack2, x);
}
}
x = pop(q.stack2);
return x;
}
/* Driver function to test above functions */
public static void main(String args[])
{
/* Create a queue with items 1 2 3*/
Queue q = new Queue();
q.stack1 = new Stack<>();
q.stack2 = new Stack<>();
enQueue(q, 1);
enQueue(q, 2);
enQueue(q, 3);
/* Dequeue items */
System.out.print(deQueue(q) + " ");
System.out.print(deQueue(q) + " ");
System.out.println(deQueue(q) + " ");
}
}
// This code is contributed by Sumit Ghosh1 2 3
Input : Q = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]Solution - The idea is to use an auxiliary stack and follow these steps to solve the problem -
k = 5
Output : Q = [50, 40, 30, 20, 10, 60, 70, 80, 90, 100]
/* Function to reverse the first K elements of the Queue */Time Complexity : O(n) , n : size of queue
void reverseQueueFirstKElements(k, Queue)
{
if (Queue.empty() == true || k > Queue.size())
return
if (k <= 0)
return
stackStack
/* Push the first K elements into a Stack*/
for ( i = 1 to k) {
Stack.push(Queue.front())
Queue.pop()
}
/* Enqueue the contents of stack
at the back of the queue*/
while (!Stack.empty()) {
Queue.push(Stack.top())
Stack.pop()
}
/* Remove the remaining elements and
enqueue them at the end of the Queue*/
for (int i = 0 to i < Queue.size() - k) {
Queue.push(Queue.front())
Queue.pop()
}
}
Input :
arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
k = 3
Output :
3 3 4 5 5 5 6
void printKMax(arr[], n, k)
{
// Create a Double Ended Queue, Qi that will store indexes of array elements
// The queue will store indexes of useful elements in every window and it will
// maintain decreasing order of values from front to rear in Qi, i.e.,
// arr[Qi.front[]] to arr[Qi.rear()] are sorted in decreasing order
deque < int > Qi(k)
/* Process first k (or first window) elements of array */
for (i = 0; i < k; ++i) {
// For every element, the previous smaller elements are useless so
// remove them from Qi
while ((!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back() // Remove from rear
// Add new element at rear of queue
Qi.push_back(i)
}
// Process rest of the elements, i.e., from arr[k] to arr[n-1]
for (; i < n; ++i) {
// The element at the front of the queue is the largest element of
// previous window, so print it
print (arr[Qi.front()])
// Remove the elements which are out of this window
while ((!Qi.empty()) && Qi.front() <= i - k)
Qi.pop_front() // Remove from front of queue
// Remove all elements smaller than the currently
// being added element (remove useless elements)
while ((!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back()
// Add current element at the rear of Qi
Qi.push_back(i)
}
// Print the maximum element of last window
print (arr[Qi.front()])
}
Asked In: Goldman Sachs Amazon
Asked In: Amazon
Asked In: Amazon
Asked In: Amazon
Asked In: Amazon FactSet Microsoft Morgan Stanley Zoho
A | When a resource is shared among multiple consumers. |
B | When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes |
C | Load Balancing |
D | All of the above |